import sys

input = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]

dp = [[None for y in x] for x in input]

m = len(input)
n = len(input[0])
for i in range(m):

    for j in range(n):
        if i == 0 and j == 0:
            dp[i][j] = input[i][j]
        else:
            up = dp[i - 1][j] if i - 1 >= 0 else sys.maxsize
            left = dp[i][j - 1] if j - 1 >= 0 else sys.maxsize
            min_val = min(up, left) + input[i][j]
            dp[i][j] = min_val

print(dp[m - 1][n - 1])
